#include <vector>

using namespace std;

// 边框为1的最大正方形
// 给你一个由若干 0 和 1 组成的二维网格 grid
// 请你找出边界全部由 1 组成的最大 正方形 子网格
// 并返回该子网格中的元素数量。如果不存在，则返回 0。
// 测试链接 : https://leetcode.cn/problems/largest-1-bordered-square/

class Solution 
{
private:
    int get(vector<vector<int>>& g, int i, int j)
    {
        return (i < 0 || j < 0) ? 0 : g[i][j];
    }

	// g : 原始二维数组
	// 把 g 变成原始二维数组的前缀和数组 sum，复用自己
	// 不能补 0 行，0列，都是 0
    void build(vector<vector<int>>& g, int m, int n)
    {
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                g[i][j] += get(g, i, j - 1) + get(g, i - 1, j) - get(g, i - 1, j - 1);
            }
        }
    }

    int sum(vector<vector<int>>& g, int a, int b, int c, int d)
    {
        return a > c ? 0 : (g[c][d] - get(g, c, b - 1) - get(g, a - 1, d) + get(g, a - 1, b - 1));
    }

public:
	// 打败比例不高，但完全是常数时间的问题
	// 时间复杂度 O(n * m * min(n,m))，额外空间复杂度 O(1)
	// 复杂度指标上绝对是最优解
    int largest1BorderedSquare(vector<vector<int>>& g) 
    {
        int m = g.size(), n = g[0].size();
        build(g, m, n);
        // 一个 1 都没有
        if(sum(g, 0, 0, m - 1, n - 1) == 0) return 0;

        // 找到的最大合法正方形的边长
        int ans = 1;
        for(int a = 0; a < m; ++a)
        {
            for(int b = 0; b < n; ++b)
            {
                // (a, b) 所有左上角点
                // (c, d) 更大边长的右下角点，k 是当前尝试的边长
                for(int c = a + ans, d = b + ans, k = ans + 1; c < m && d < n; ++c, ++d, ++k)
                {
                    if(sum(g, a, b, c, d) - sum(g, a + 1, b + 1, c - 1, d - 1) == (k - 1) << 2)
                    {
                        ans = k;
                    }
                }
            }
        }
        return ans * ans;
    }
};